package com.xzq.Hot100;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Author xzq
 * @Description //两数之和
 * @Date 2021/12/6 17:31
 * @Version 1.0.0
 **/
public class Demo01 {
    public static void main(String[] args) {
        int[] array = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(array, target);
        System.out.println(Arrays.toString(result));
    }

    //时间复杂度 O(n的平方)
//    public  static int[] twoSum(int[] nums, int target) {
//        for (int i = 0; i < nums.length-1; i++) {
//            for (int j = i+1; j < nums.length; j++) {
//                if ((nums[i] + nums[j]) == target) {
//                    return new int[]{i, j};
//                }
//            }
//        }
//        return null;
//    }
    //时间复杂度O(n)   执行耗时 2 ms   内存消耗:38.4 MB
//    public static int[] twoSum(int[] nums, int target) {
//        HashMap<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            int source = target - nums[i];
//            if (map.containsKey(source)) {
//                return new int[]{map.get(source), i};
//            }
//            map.put(nums[i], i);
//        }
//        return null;
//    }

    //时间复杂度O(N)  减少一些中间变量  最优解
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target-nums[i], i);
        }
        return null;
    }

}
